package com.minigame.leetCode;

import java.util.Arrays;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 给你一个整数数组 faces ，表示不同面额的币面值；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的币面值组合 。如果没有任何一种币面值组合能组成总金额，返回空 。
 * 你可以认为每种币面值的数量是无限的。
 *
 * 示例1：
 * 输入：faces = [1, 2, 5], amount = 11
 * 输出：[5, 5, 1]
 *
 * 示例 2：
 * 输入：faces = [2], amount = 3
 * 输出：[]
 *
 */
public class CashPayer {

    public static int[][] distinct(int[][] dp) {
        Set<String> set = Arrays.stream(dp).map(arr -> Arrays.stream(arr).mapToObj(Objects::toString).collect(Collectors.joining(":"))).collect(Collectors.toSet());
        int[][] r = new int[set.size()][];
        int i = 0;
        for (String s : set) {
            String[] split = s.split(":");
            r[i] = new int[split.length];
            for (int j = 0; j < split.length; j++) {
                r[i][j] = Integer.parseInt(split[j]);
            }
            i++;
        }
        return r;
    }

    public static int[][] pays(int amount, int[] faces) {
        int[][][] dp = new int[amount + 1][][];
        dp[0] = new int[1][faces.length];
        for (int i = 1; i < amount + 1; i++) {
            dp[i] = new int[0][faces.length];
            for (int j = 0; j < faces.length; j++) {
                if (faces[j] <= i) {
                    deepCopyAndPlus(dp, faces[j], i, j);
                }
            }
        }
        return distinct(dp[amount]);
    }

    public static void deepCopyAndPlus(int[][][] dp, int face, int i, int j) {
        int srcLength = dp[i].length;
        dp[i] = Arrays.copyOf(dp[i], srcLength + dp[i - face].length);
        for (int k = 0; k < dp[i - face].length; k++) {
            dp[i][srcLength + k] = Arrays.copyOf(dp[i - face][k], dp[i - face][k].length);
            dp[i][srcLength + k][j]++;
        }
    }

    public static int[] pay(int amount, int[] faces) {
        int[][] dp = new int[amount + 1][faces.length];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < faces.length; j++) {
                dp[i][j] = i == 0 ? 0 : (amount + 1);
            }
        }
        for (int i = 1; i <= amount; i++) {
            for (int k = 0; k < faces.length; k++) {
                if (faces[k] <= i) {
                    int sum1 = Arrays.stream(dp[i]).reduce(Integer::sum).orElse(0);
                    int sum2 = Arrays.stream(dp[i - faces[k]]).reduce(Integer::sum).orElse(0) + 1;
                    int min = Math.min(sum1, sum2);
                    if (min == sum2) {
                        dp[i] = Arrays.copyOf(dp[i - faces[k]], faces.length);
                        dp[i][k]++;
                    }
                }
            }
        }
        return dp[amount][0] > amount ? new int[]{} : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println("=====最优组合=====");
        System.out.println(Arrays.toString(pay(11, new int[]{5,2,1})));
        System.out.println("=====全部组合=====");
        for (int[] pay : pays(11, new int[]{5, 2, 1})) {
            System.out.println(Arrays.toString(pay));
        }
    }
}
